package 剑指offer.第2天;

import java.util.Stack;

/**
 * 剑指 Offer 24. 反转链表
 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 示例:
 输入: 1->2->3->4->5->NULL
 输出: 5->4->3->2->1->NULL
 */
public class Solution2 {
    /**递归解法，巧妙就巧妙在不操作node。可以一直返回回来。
     * @param head
     * @return
     */
    public ListNode reverseList0(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    public ListNode reverseList1(ListNode head) {
        //如果链表为空，或者只有一个元素，则直接返回该链表
        if (head==null||head.next==null){
            return head;
        }
        //定义一个辅助节点遍历原来的链表 可以不用
//        ListNode cur=head;
        //指向下一个节点
        ListNode next=null;
        ListNode  newNode= new ListNode(0);
        while (head!=null){
            //存储cur 的下一个节点
            next=head.next;
            head.next=newNode.next;// 当前指针下一个节点是倒序的新节点
            newNode.next=head;
            head=next;
        }
        return newNode.next;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode root = new ListNode(1);
//        ListNode pre = root;
        ListNode cur = head;
        while (cur != null){
            ListNode temp = cur.next;
            cur.next = root.next;
            root.next = cur;
            cur = temp;
        }
/* 可以不用pre
        ListNode root = new ListNode(1);
        ListNode pre = root;
        ListNode cur = head;
        while (cur != null){
            ListNode temp = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = temp;
        }
*/
        return root.next;
    }
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(3);
        node.next.next = new ListNode(2);
        node.next.next.next = new ListNode(5);

        ListNode listNode = new Solution2().reverseList_stack(node);
        System.out.println("listNode = " + listNode);
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 迭代法
     */
    public ListNode reverseList_1(ListNode head) {
        ListNode newHead = null;
        while (head != null){
            // 1、4用于遍历
            ListNode temp = head.next;
            // 2、3用于反转链表
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    /**
     * 递归法
     */
    public ListNode reverseList_recursion(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList_recursion(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    /**
     * 借助栈
     */
    public ListNode reverseList_stack(ListNode head) {
        if (head == null) return head;
        Stack<ListNode> stack = new Stack<>();
        while (head!=null){
            stack.push(head);
            head = head.next;
        }
        ListNode newHead = stack.pop();
        ListNode tailNode = newHead;
        while (!stack.isEmpty()){
            ListNode cur =  stack.pop();
            tailNode.next = cur;
            tailNode = cur;
        }
        tailNode.next = null;
        return newHead;
    }
}


